package algorithm.backtracking.basic;

/**
 * 项目名称: god
 * 包 名 称: algorithm.backtracking.basic
 * 类 名 称: Queens2
 * 类 描 述: TODO
 * 创建时间: 2020/7/11 8:32 上午
 * 创 建 人: Justice
 */
public class Queens2 {
    /**
     * 数组索引是行号，数组元素是列号
     */
    int[] queens;
    /**
     * 标记着某一列是否有皇后
     */
    boolean[] cols;
    /**
     * 标记着某一斜线上是否有皇后（左上角 -> 右下角）
     */
    boolean[] leftTop;
    /**
     * 标记着某一斜线上是否有皇后（右上角 -> 左下角）
     */
    boolean[] rightTop;
    /**
     * 一共有多少种摆法
     */
    int ways;

    public void placeQueens(int n) {
        if (n < 1) return;
        queens = new int[n];
        cols = new boolean[n];
        leftTop = new boolean[(n << 1) - 1];
        rightTop = new boolean[leftTop.length];
        place(0);
        System.out.println(n + "皇后一共有" + ways + "种摆法");
    }

    // 从第row行开始摆放皇后
    public void place(int row) {
        if (row == cols.length) {
            ways++;
            show();
            return;
        }
        for (int col = 0; col < cols.length; col++) {
            if (cols[col]) continue;
            int ltIndex = row - col + cols.length - 1;
            if (leftTop[ltIndex]) continue;
            int rlIndex = row + col;
            if (rightTop[rlIndex]) continue;

            // 记录元素位置
            queens[row] = col;

            cols[col] = true;
            leftTop[ltIndex] = true;
            rightTop[rlIndex] = true;
            place(row + 1);
            // 回溯加重置
            cols[col] = false;
            leftTop[ltIndex] = false;
            rightTop[rlIndex] = false;
        }
    }

    public void show() {
        for (int row = 0; row < cols.length; row++) {
            for (int col = 0; col < cols.length; col++) {
                if (queens[row] == col) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println("------------------------------");
    }
}
